#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    bool GetqSize(TreeNode* root, TreeNode* r, stack<TreeNode*>& que)
    {
        if (root == nullptr)
            return false;

        que.push(root);

        if (root->val == r->val)
            return true;

        if (GetqSize(root->left, r, que))
            return true;

        if (GetqSize(root->right, r, que))
            return true;

        que.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> que1;
        stack<TreeNode*> que2;
        GetqSize(root, p, que1);
        GetqSize(root, q, que2);

        // TreeNode* tmp = que1.top();
        // TreeNode* tmp2 = que2.top();
        // cout<<tmp->val<<endl;
        // cout<<tmp2->val<<endl;
        while (que1.size() > que2.size())
        {
            que1.pop();
        }
        while (que1.size() < que2.size())
        {
            que2.pop();
        }
        while (que1.top() != que2.top())
        {
            que1.pop();
            que2.pop();
        }
        return que1.top();
    }
};